package com.data.basic.chapter08;


import java.util.*;

/**
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

 例如，

 给定数组 [1,1,1,2,2,3] , 和 k = 2，返回 [1,2]。

 注意：

 你可以假设给定的 k 总是合理的，1 ≤ k ≤ 数组中不相同的元素的个数。
 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小
 */

/**
 * 用java的自己的优先队列来实现，java默认最小堆
 */
public class LeetCode347byJava {

    private class  Freq implements Comparable<Freq>{
        // e表示元素
        //  freq:表示频次
       public int e, freq;

        public Freq(int key, Integer integer) {
            this.e = key;
            this.freq = integer;
        }

        // 频次小，优先级高
        public int compareTo(Freq other) {
            if (this.freq>other.freq){
                return 1;
            }else if (this.freq==other.freq){
                return 0;
            }
            return -1;
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        // 单词计数
        TreeMap<Integer,Integer> map = new TreeMap<Integer, Integer>();

        for (int num:nums){
            if (map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }
            else {
                map.put(num,1);
            }

        }

        PriorityQueue<Freq> pq = new PriorityQueue<Freq>();
        for(int key:map.keySet()){
            if (pq.size()<k){// 队列中的元素还未达到
                pq.add(new Freq(key,map.get(key)));
            }else if (map.get(key)>pq.peek().freq){//看一眼队首的元素
                pq.remove();
                pq.add(new Freq(key,map.get(key)));

            }
        }
        LinkedList<Integer> res = new LinkedList<Integer>();
        while (!pq.isEmpty()){
            res.add(pq.remove().e);
        }
        return res;

    }


}
